#include <cstdlib>
#include <unordered_map>

using namespace std;

class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

class Solution {
private:
    Node* helper(Node* node, unordered_map<Node*, Node*>& map) {
        if (node == nullptr) {
            return node;
        }
        if (map.find(node) != map.end()) {
            return map[node];
        }
        Node* new_node = new Node(node->val);
        map[node] = new_node;
        new_node->next = helper(node->next, map);
        new_node->random = helper(node->random, map);
        return new_node;
    }
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> map;
        return helper(head, map);
    }
};
